原贴地址：[http://blog.leanote.com/post/dawnmagnet/lc278-374-852](http://blog
.leanote.com/post/dawnmagnet/lc278-374-852)
# 写在前面
二分查找是一个非常基础的算法。但是完全掌握却并不容易。
首先再次介绍一下二分查找。
大家开始学习二分的时候，总是伴随着一个万年不变的场景：有序数组(假设是升序)。
核心思路就是判断num[mid]。
但是大家一开始学的都会有三种情况。
- num[mid] > target，就表示要找的数字一定位于mid左边，所以我们将右边界限制到m
id-1，也就是right = mid - 1;
- num[mid] == target，刚好找到，返回mid。
- num[mid] < target，就表示要找的数字一定位于mid右边，所以我们将左边界限制到m
id+1，也就是left = mid + 1;
这个例子非常好，确实讲出来了二分查找的核心思路，但忽略了许多细节。
在写二分查找的时候，是否总是写出来TLE（超出时间限制/死循环）？是否总是不能获
得想要的答案？
在看完这篇专题之后，一定能启发你有所思考。
# 二分查找的特解
众所周知，一个通用的二分查找是不一定有特解的。
也就是说，在查找之前，我们是不知道数组中有没有我们需要查找的那个值的。也有可
能有多个target，此时返回任意一个不确定的target的位置是没有意义的（这时候人们
往往更加关系第一个target和最后一个target的位置）。
所以刚才介绍的num[mid] == target这种情况，是**完全**没有意义的。
在所有需要用到二分查找的工业/商业场景，没有人会去判断一个等于的情况。
我们就要总结出一个更通用的规律。
将等于的情况并入大于或者是小于，也就是变成了大于等于和小于等于。
这样就将3种情况变成了两种情况，而且对于最终的结果没有任何的影响，不管是否有ta
rget我们都能返回，甚至在有多个target的时候，还能返回target的左边界和右边界。
既然有左边界和右边界，我们需要如何操作才能返回左边界和右边界呢？如何在代码中
区分这两种情况呢？
# 二分查找的“靠左”和“靠右”和边界
二分查找的中间值的取法也是一个很重要的细节。
我们一般使用的是`mid=(left+right)/2`，这样获得是靠左的中间值。
对于一个奇数长度的(由left和right包围的)数组来说，中间值只有一个，但是对于一个
偶数长度的数组来说，中间值有两个，而且并不相同。
那么我们在两个中间值中，只能选取一个，那么这个选取的方法对于最终的结果有影响
吗？
我们设想这么一个场景，假设二分到了最后一步，此时只剩下两个数了。
![title](https://img-blog.csdnimg.cn/img_convert/3e98e88cd08e7589429cf17fbd65
ec2e.png)
如果我们“靠左”取mid，那么就会出现如上图所示的情况，如果我们的代码像下面一样，
肯定是不可行的：